#include "./double-linked-list.h"
#include <stdlib.h>
#include <stdio.h>

DoubleLinkedList createDoubleLinkedList(int array[], int n)
{
	DoubleLinkedList list = (DLNode *)malloc(sizeof(DLNode));
	list->data = 0;
	list->next = list->prior = NULL;
	int i;
	DLNode *pointer = list;
	for (i = 0; i < n; i++)
	{
		DLNode *node = (DLNode *)malloc(sizeof(DLNode));
		node->data = array[i];
		node->next = pointer->next;
		node->prior = pointer;
		pointer->next = node;
		pointer = pointer->next;
	}
	return list;
}

void doubleListInsert(DoubleLinkedList list, int data, int index)
{
	// 索引到index的前一个
	DLNode *pointer = getDoubleListNode(list, index - 1);
	if (pointer == NULL)
	{
		return;
	}
	// 新结点
	DLNode *node = (DLNode *)malloc(sizeof(DLNode));
	node->data = data;
	// 新插入结点，先设定新结点前驱和后驱
	node->next = pointer->next;
	node->prior = pointer;
	// 然后分别调整指针结点的后驱及其后驱结点的前驱
	// 注意判断指针结点后可能为NULL（尾部插入时）
	if (pointer->next != NULL)
	{
		pointer->next->prior = node;
	}
	pointer->next = node;
}

void doubleListDelete(DoubleLinkedList list, int index)
{
	// 索引到index的前一个
	DLNode *pointer = getDoubleListNode(list, index - 1);
	if (pointer == NULL)
	{
		return;
	}
	// 先标记被删除结点
	DLNode *remove = pointer->next;
	// 若index - 1为最后一个
	if (remove == NULL)
	{
		return;
	}
	// 然后调整指针结点的后驱为被删除结点后驱
	pointer->next = remove->next;
	// 调整原被删除结点的后驱的前驱，注意判断空（尾部删除时）
	if (remove->next != NULL)
	{
		remove->next->prior = pointer;
	}
	free(remove);
}

DLNode *getDoubleListNode(DoubleLinkedList list, int index)
{
	// 头结点下标视为-1
	int i = -1;
	DLNode *pointer = list;
	while (pointer != NULL && i < index)
	{
		pointer = pointer->next;
		i++;
	}
	return pointer;
}

void printDoubleList(DoubleLinkedList list)
{
	DLNode *pointer = list;
	printf("O");
	while ((pointer = pointer->next) != NULL)
	{
		printf(" <-> %d", pointer->data);
	}
	printf(" <-> ^\n");
}